export class Stack {
    constructor(
        public contents: string[]
    ) {

    }

    push(character: string) {
        let newContents = [character]
        this.contents.forEach(c => {
            newContents.push(c)
        })
        return new Stack(newContents)
    }

    pop() {
        let newContents = [];
        // 忽略第一个
        for (let index = 1; index < this.contents.length; index++) {
            newContents.push(this.contents[index])
        }
        return new Stack(newContents)
    }

    top() {
        return this.contents[0]
    }

    toString() {
        return this.contents.toString()
    }
}

// let stack = new Stack(['a','b','c','d','e'])
// console.log(stack)
// console.log(stack.top(),stack)
// console.log(stack.pop().pop().top(),stack)
// console.log(stack.push('x').push('y').pop().top(),stack)

// 当前状态的定义
export class PDAConfiguration {
    STUCK_STATE = -1
    constructor(
        public state: number,
        public stack: Stack
    ) { }

    stuck(){
        return new PDAConfiguration(this.STUCK_STATE,this.stack)
    }
    isStuck(){
        return this.state == this.STUCK_STATE
    }
}

// 转换过程的定义
// 匹配条件
// 转换的目的和栈的操作
export class PDARule {
    constructor(
        // 匹配状态
        public state: number,
        // 匹配字符
        public character: string,
        // 目标状态
        public next_state: number,

        // 匹配栈顶
        public pop_character: string,
        // 修改栈
        public push_characters: string[]
    ) { }

    applies_to(config: PDAConfiguration, character: string) {
        return this.state == config.state
            && this.pop_character == config.stack.top()
            && this.character == character
    }
    follow(config: PDAConfiguration) {
        return new PDAConfiguration(
            this.next_state,
            this.next_stack(config)
        )
    }
    next_stack(config: PDAConfiguration) {
        //弹出后新的栈
        let popped_stack = config.stack.pop();
        // Array.reverse 颠倒顺序会修改原数组
        for (let index = this.push_characters.length - 1; index >= 0; index--) {
            popped_stack = popped_stack.push(this.push_characters[index])
        }
        return popped_stack
    }
}
// 规则的定义
class DPDARuleBook {
    constructor(
        public rules: PDARule[]
    ) { }

    next_config(config: PDAConfiguration, character: string) {
        let rule =  this.rule_for(config, character)
        return rule?.follow(config)
    }

    rule_for(config: PDAConfiguration, character: string): PDARule | null {
        let next_rule: PDARule | null = null;
        for (let index = 0; index < this.rules.length; index++) {
            const rule = this.rules[index];
            if (rule.applies_to(config, character)) {
                next_rule = rule
                break;
            }
        }
        return next_rule
    }
    applie_to(config:PDAConfiguration,character:string){
        return !!this.rule_for(config,character) 
    }
    follow_free_moves(config:PDAConfiguration){
        if(this.applie_to(config,'')){
            config = this.next_config(config,'') as PDAConfiguration;
            this.follow_free_moves(config)
        }
        return config
    }
}
class DPDA {
    constructor(
        public current_config:PDAConfiguration,
        public accept_states:number[],
        public rulebook:DPDARuleBook
    ){}
    accepting(){
       return this.accept_states.includes(this.current_config.state)
    }
    read_character(character:string){
        //计算自由移动
        this.current_config = this.next_config(character)
        if(!this.isStuck()){
            this.current_config = this.rulebook.follow_free_moves(
                this.current_config
            )
        }
    }
    next_config(character:string){
        let result :PDAConfiguration;
        if(this.rulebook.applie_to(this.current_config,character)){
            result = this.rulebook.next_config(this.current_config,character) as PDAConfiguration
        }else{
            result = this.current_config.stuck()
        }
        return result
    }
    isStuck(){
        return this.current_config.isStuck()
    }
    read_string(input:string){
        let inputArray = input.split('');
        inputArray.forEach(s => {
            if(!this.isStuck()){
                this.read_character(s)
            }
        })
    }
}

class DPDADesign{
    constructor(
        public start_state:number,
        public bootom_character:string,
        public accept_states:number[],
        public rulebook:DPDARuleBook
    ){}

    accpts(input:string){
        let dpda = this.to_dpda()
        dpda.read_string(input)
        return dpda.accepting()
    }

    to_dpda(){
        let start_stack = new Stack([this.bootom_character])
        let start_config = new PDAConfiguration(
            this.start_state,start_stack
        )
        return new DPDA(start_config,this.accept_states,this.rulebook)
    }
}
// let State1 = number(1)
// let State2 = number(2)

// let rule = new PDARule(
//     State1, '$', '(', State2,
//     ['b', '$']
// )
// let config = new PDAConfiguration(
//     State1, new Stack(['$'])
// )

// console.log(rule.applies_to(config, '('))
// console.log(rule.follow(config))

let ruleBook = new DPDARuleBook([
    new PDARule(1, '(', 2, '$', ['b', '$']),
    new PDARule(2, '(', 2, 'b', ['b', 'b']),
    new PDARule(2, ')', 2, 'b', []),
    new PDARule(2, '', 1, '$', ['$']),
])

// let config = new PDAConfiguration(
//     1, new Stack(['$'])
// )

// config = ruleBook.next_config(config, '(')
// console.log(config)
// config = ruleBook.next_config(config, '(')
// console.log(config)
// config = ruleBook.next_config(config, ')')
// console.log(config)


// let dpda = new DPDA(new PDAConfiguration(1,new Stack(['$'])),[1],ruleBook)

// console.log(dpda.accepting())
// dpda.read_string('((()')
// console.log(dpda.accepting())
// console.log(dpda.current_config)

// let config = new PDAConfiguration(2,new Stack(['$']))
// console.log(ruleBook.follow_free_moves(config))

// let dpda = new DPDA(
//    new PDAConfiguration(1,new Stack(['$'])),
//    [1],
//    ruleBook
// )
// console.log(dpda.current_config)
// dpda.read_string('(()(')
// console.log(dpda.current_config)
// dpda.read_string('))()')
// console.log(dpda.current_config)

// let dpda_design = new DPDADesign(1,'$',[1],ruleBook)
// console.log(dpda_design.accpts('((((((()))))))'))
// console.log(dpda_design.accpts('()(())((()))(())()'))
// console.log(dpda_design.accpts('())'))




